class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int upper = 0;
        //找到数组中最大的元素，定义一个数组可以包含所有数字
        for(int x : arr1) {
            upper = Math.max(upper,x);
        }

        //遍历arr1存在+1
        int[] aa = new int[upper+1];
        for(int x:arr1) {
            aa[x]++;
        }

        //遍历数组arr2，arr1有放入
        int[] ans = new int[arr1.length];
        int index = 0;
        for(int x:arr2) {
            for(int i = 0;i < aa[x];i++) {
                ans[index] = x;
                index++;
            }
            aa[x]=0;
        }


        //遍历aa，不为0， 加入[可能是多个遍历]
        for(int i = 0;i <= upper;i++) {
            for(int j = 0;j < aa[i];j++) {
                ans[index] = i;
                index++;
            }
        }
        return ans;
    }
}